1. Field of the Invention
The present invention pertains generally to array multipliers, and more particularly to a Booth-encoded array multiplier architecture wherein low transition probability partial-products are generated, and the adder array is re-arranged according to the partial-products' signal transition probabilities.
2. Description of the Background Art
Multiplication is a ubiquitous operation in digital signal processing (DSP) applications. The well-known modified Booth-encoding algorithm reduces the number of partial products that must be added and is widely used in VLSI implementations of multiplication. Referring to FIG. 1, a Booth-encoded multiplier 10 typically comprises the following elements: a Booth-encoder 12, a partial-product generator 14, a partial-product summation array 16, and a final carry-propagation adder 18.
The radix-4 Booth encoding algorithm is commonly used in DSP applications. For multiplication XY, the radix-4 Booth-encoding algorithm encodes an N-bit two's complement number Y, one bit-pair at a time, into a set of signed-digits
  (            S              0        ,              ,          S                        N          2                -        1              )according to Table 1. In FIG. 1, S0 is the least significant digit (LSD) and
  S            N      2        -    1  is the most-significant digit (MSD). To reduce the switching activity, and hence the power dissipation, in the partial-product generators and the adders, it is understood to be preferable to encode both a string of zeros and a string of ones as +0, as indicated by the bold +0 entries in Table 1. We define such a Booth-encoding method as “+0 Booth-encoding”. See, for example, C. J. Nicol and P. Larsson, “Low power multiplication for FIR filters,” in Proceedings of International Symposium on Low Power Electronics and Design, August 1997, pp. 76–79, incorporated herein by reference.
The partial-product generator 14 produces a partial-product Qi (generated using a simple shift and complement) according to multiplicand X and a signed-digit Si. In FIG. 1, Q0 is the LSD partial-product and it has the shortest word-length.
Referring to FIG. 2, as an example, a “standard” 8×8 Booth-encoded carry-save array multiplier 50 is shown. As used herein, the term “standard” means a conventional array multiplier structure with or without Booth-encoding wherein partial-products are added sequentially from the LSD partial-product to the MSD partial-product. By way of example, and not of limitation, FIG. 2 shows a “standard” array multiplier of the carry-save type. A standard carry-save array is a regular structure in which the partial-products are added together sequentially, with increasing word-length, starting with the LSD partial-product Q0. In other words, a standard array multiplier adds the partial-products starting with the shorter word-lengths. Note that the sign-extensions of the two's complement numbers are taken care of by a compensation vector added in the adder array. See, for example, L. K. Tan, “High performance multiplier and adder compilers,” M.S. thesis, UCLA, 1992, incorporated herein by reference. Other partial-product summation techniques can be employed in a manner that will be compatible with the present invention. In addition to carry-save adders, for example, the use of 4-to-2 compressors and dual-carry-save arrays can be employed, as will be evident to one skilled in the art.
As can be seen, the well-known modified Booth-encoding algorithm reduces the number of partial-products and is widely used in multipliers for DSP applications. The use of +0 Booth-encoding can reduce the transition probability of the partial-products. However, the switching of the partial products causes signal transitions in the partial-product adder array, and spurious transitions and logic races that flow through the adder array are major sources of power dissipation in multipliers. Accordingly, there is a need for an array configuration where unnecessary switching activity in the array is reduced.